Теорема о разложении восходящего факториала

$$x^{\overline{n}} = \sum_{k=0}^{n} \begin{bmatrix} n \\ k \end{bmatrix} x^k$$

Пусть коэффициент при $x^k$ в разложении $x^{\overline{n}}$ равен $f(n, k)$. Докажем, что $f(n, k)$ удовлетворяет рекуррентному соотношению для $\begin{bmatrix} n \\ k \end{bmatrix}$. Распишем $x^{\overline{n+1}} = x(x+1)\dots(x+n-1)(x+n) = n \cdot x^{\overline{n}} + x \cdot x^{\overline{n}}$. Коэффициент при $x^k$ в левой части равен $f(n+1, k)$, а в правой $n \cdot f(n, k) + f(n, k-1)$, и они равны. Следовательно, $f(n, k)$ задается тем же рекуррентным соотношением, что и $\begin{bmatrix} n \\ k \end{bmatrix}$. Проверим начальные условия. $f(n, 0) = 0$ при $n > 0$, так как есть множитель $x$. $f(n, n) = 1$, так как $x^n$ получается перемножением иксов из всех скобок. Начальные условия тоже выполнены, следовательно $f(n, k) = \begin{bmatrix} n \\ k \end{bmatrix}$. $\square$